package optimizers.ganeat.novisual;


import fitness.FitnessResult;


import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.CompletionService;
import java.util.concurrent.ExecutorCompletionService;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

import model.OligoSystemGeneral;

import optimizers.commons.GAConstants;
import optimizers.commons.RunConfig;
import optimizers.commons.evaluator.FitnessEvaluationService;
import optimizers.ganeat.report.LoggerNEAT;


import optimizers.ganeat.*;

public abstract class GA {

	protected Random rand = new Random();
	public Map<String, Integer> innovations;
	public Map<String, String> nodeNames;
	protected int maxRunTime = 30;
	ExecutorService eservice;
	protected CompletionService<Object> cservice;
	protected FitnessEvaluationService evaluationService;
	ArrayList<Individual> speciesLib;
	protected RunConfig config;

	public GA(RunConfig config) {
		innovations = new HashMap<String, Integer>();
		nodeNames = new HashMap<String, String>();
		speciesLib = new ArrayList<Individual>();
		this.config = config;
	}

	public abstract Individual getInitialIndividual();

	public abstract Individual getNewIndividual(
			Map<String, Integer> innovations2, Map<String, String> nodeNames2,
			int i, int j);

	public abstract String getProblemName();

	public void run() throws CloneNotSupportedException {
		DateFormat dateFormat = new SimpleDateFormat("yyyy_MM_dd HH_mm_ss");
		Date date = new Date();
		String fileName = "result/NEAT_" + getProblemName() + "_"
				+ dateFormat.format(date);
		Individual indiv = getInitialIndividual();
		Individual newSpecies = clone(indiv);
		speciesLib.add(newSpecies);
		Individual[] nextGen = new Individual[Constants.popSize];
		double[] fitness = new double[Constants.popSize];
		eservice = Executors.newFixedThreadPool(Integer.parseInt((String) config.properties.get("threads")));
		cservice = new ExecutorCompletionService<Object>(eservice);
		double[][] speciesData = new double[2][Constants.generations + 1];
		ArrayList<ArrayList<Species>> speciesVisualData = new ArrayList<ArrayList<Species>>();
		LoggerNEAT logger = new LoggerNEAT(fileName, true, speciesVisualData,
				speciesData, innovations, nodeNames, speciesLib, config);

		evaluationService = new FitnessEvaluationService(cservice,
				config.evaluator, maxRunTime);
		
		// System.out.println("Displaying 1st individual");
		
		// System.out.println("End Displaying 1st individual");
		/*
		 * JFrame speciesFrame = new JFrame("Species");
		 * speciesFrame.setSize(1300, 700); JTabbedPane tabbedPane = new
		 * JTabbedPane(); speciesFrame.add(tabbedPane);
		 * speciesFrame.setVisible(true);
		 */

		

		// generation loop
		for (int generation = 0; generation <= Constants.generations; generation++) {
			logger.logToMemory("Generation " + generation);
			if (generation == 0) { // initial generation
				for (int i = 0; i < Constants.popSize; i++) {
					nextGen[i] = clone(indiv);
					nextGen[i].generationIndex = generation;
					nextGen[i].individualIndex = i;
					nextGen[i].mutate();
				}
			} else { // from 1st generation
				int i = 0;
				ArrayList<Species> thisGenSpecies = speciesVisualData
						.get(generation - 1);
				for (Species sp : thisGenSpecies) {
					int nextGenPop = sp.getNextGenPopulation();
					if (sp.getNextGenPopulation() > 0) {
						nextGen[i] = clone(sp.getBestIndividual());
						nextGen[i].generationIndex = generation;
						nextGen[i].individualIndex = i;
						i++;
						nextGenPop--;
					}
					int nToRemove = Math.min(sp.individuals.size() / 2,
							sp.individuals.size() - 2);
					System.out.println("Removing " + nToRemove);
					for (int j = 0; j < nToRemove; j++) {
						Individual indivToRemove = sp.individuals.get(0);
						for (Individual indiv1 : sp.individuals) {
							if (indivToRemove.getFitness() > indiv1
									.getFitness()) {
								indivToRemove = indiv1;
							}
						}
						sp.individuals.remove(indivToRemove);
					}
					for (int j = 0; j < nextGenPop; j++) {
						if (rand.nextDouble() < Constants.probMutationOnly) {
							Individual[] parents = selectCrossoverParents(sp.individuals);
							nextGen[i] = clone(parents[0]);
							nextGen[i].mutate();
							nextGen[i].generationIndex = generation;
							nextGen[i].individualIndex = i;
							nextGen[i].parent1 = parents[0];
							nextGen[i].parent2 = parents[0];
						} else {
							if (rand.nextDouble() < Constants.interspeciesMatingRate) {
								System.out.println("b");
								Species interSpecies = null;
								do {
									interSpecies = thisGenSpecies.get(rand
											.nextInt(thisGenSpecies.size()));
								} while (interSpecies != sp);
								Individual[] parents1 = selectCrossoverParents(sp.individuals);
								Individual[] parents2 = selectCrossoverParents(interSpecies.individuals);
								nextGen[i] = crossOver1Point(parents1[0], parents2[0]);
								nextGen[i].generationIndex = generation;
								nextGen[i].individualIndex = i;
								nextGen[i].parent1 = parents1[0];
								nextGen[i].parent2 = parents2[0];
								if (this.rand.nextDouble() < Constants.probIndividualMutation) {
									nextGen[i].mutate();
								}
							} else {
								Individual[] parents = selectCrossoverParents(sp.individuals);
								nextGen[i] = crossOver1Point(parents[0], parents[1]);
								nextGen[i].generationIndex = generation;
								nextGen[i].individualIndex = i;
								nextGen[i].parent1 = parents[0];
								nextGen[i].parent2 = parents[1];
								if (this.rand.nextDouble() < Constants.probIndividualMutation) {
									nextGen[i].mutate();
								}
							}
						}
						i++;
					}
				}
				System.out.println("Done removing");

				// fill the rest with mutation only
				while (i < Constants.popSize) {
					Species randomSpecies = thisGenSpecies.get(rand
							.nextInt(thisGenSpecies.size()));
					Individual parents = randomSpecies.individuals.get(rand
							.nextInt(randomSpecies.individuals.size()));
					nextGen[i] = clone(parents);
					nextGen[i].mutate();
					nextGen[i].generationIndex = generation;
					nextGen[i].individualIndex = i;
					nextGen[i].parent1 = parents;
					nextGen[i].parent2 = parents;
					i++;
				}
			}

			int count = 0;
			for (int i = 0; i < Constants.popSize; i++) {
				if (nextGen[i].mutationInfo.contains("(-)")) {
					count++;
				}
			}
			System.out.println("Switch mutation happened " + count + " times.");
			// Evaluate fitness in parallel

			// Launch all evaluations. Separate function, so that it can be
			// easily overridden by children.
			launchEvaluation(nextGen, logger);
			postEvaluation(nextGen);
			System.out.println("Error Individuals ");
			for (int i = 0; i < nextGen.length; i++) {
				if (nextGen[i].fitnessResult == null) {
					System.out.println(nextGen[i].toString());
					System.out.println("-------------------");
				}
			}

			int bestIndividualIndex = 0;
			for (int i = 1; i < nextGen.length; i++) {
				if (nextGen[bestIndividualIndex].getFitness() < nextGen[i]
						.getFitness()) {
					bestIndividualIndex = i;
				}
			}

			
			// Speciation
			System.out.println("Start speciation");
			for (int i = 0; i < nextGen.length; i++) {
				// compare with previous species' best individuals
				if (generation > 0) {
					double curSpeciesFitness = 0;
					for (Species sp : speciesVisualData.get(generation - 1)) {
						Individual bestIndiv = sp.getBestIndividual();
						if (curSpeciesFitness < bestIndiv.getFitness()) {
							if (compDistance(nextGen[i], bestIndiv) < Constants.speciationThreshold) {
								nextGen[i].spicies = sp.representative;
								nextGen[i].indivCompared = bestIndiv;
								curSpeciesFitness = bestIndiv.getFitness();
							}
						}
					}
				}

				// compare with every individual in previous generation
				if (nextGen[i].spicies == null && generation > 0) {
					for (Species sp : speciesVisualData.get(generation - 1)) {
						for (Individual indiv1 : sp.individuals) {
							if (compDistance(nextGen[i], indiv1) < Constants.speciationThreshold) {
								nextGen[i].spicies = sp.representative;
								nextGen[i].indivCompared = indiv1;
								break;
							}
						}
					}
				}

				// compare with history species
				if (nextGen[i].spicies == null) {
					for (Individual indiv1 : speciesLib) {
						if (compDistance(nextGen[i], indiv1) < Constants.speciationThreshold) {
							nextGen[i].spicies = indiv1;
							nextGen[i].indivCompared = indiv1;
							break;
						}
					}
				}

				// make new species
				if (nextGen[i].spicies == null) {
					newSpecies = clone(nextGen[i]);
					speciesLib.add(newSpecies);
					nextGen[i].spicies = newSpecies;
					nextGen[i].indivCompared = null;
					System.out.println("-------->Species added: "
							+ newSpecies.generationIndex + ","
							+ newSpecies.individualIndex);
				}

			}

			ArrayList<Species> nextGenSpecies = new ArrayList<Species>();
			for (Individual species : speciesLib) {
				Species sp = new Species(species);
				/*
				 * if (generation > 0) { for (Species sp1 :
				 * speciesVisualData.get(generation - 1)) { if
				 * (sp1.representative == sp.representative) { for (Individual
				 * indiv1 : sp1.individuals) { sp.individuals.add(indiv1); } } }
				 * }
				 */
				for (int i = 0; i < nextGen.length; i++) {
					if (nextGen[i].spicies == sp.representative) {
						sp.individuals.add(nextGen[i]);
					}
				}
				if (sp.individuals.size() > 0) {
					nextGenSpecies.add(sp);
				}
			}
			speciesVisualData.add(nextGenSpecies);

			// calculate next gen population for each species
			ArrayList<Species> cappedSpecies = new ArrayList<Species>();
			int popSizeLeft = Constants.popSize;
			// calculate 1st time
			double sumFitness = 0;
			for (Species sp : nextGenSpecies) {
				sumFitness += sp.getSpeciesFitness();
			}
			for (Species sp : nextGenSpecies) {
				int nextGenPop = (int) (sp.getSpeciesFitness() * popSizeLeft / sumFitness);
				// capping
				if (nextGenPop > sp.individuals.size() + Constants.popSize / 10) {
					nextGenPop = sp.individuals.size() + Constants.popSize / 10;
					sp.setNextGenPopulation(nextGenPop);
					cappedSpecies.add(sp);
					popSizeLeft -= nextGenPop;
				}
			}

			// calculate 2nd time removing the capped species
			sumFitness = 0;
			for (Species sp : nextGenSpecies) {
				if (!cappedSpecies.contains(sp)) {
					sumFitness += sp.getSpeciesFitness();
				}
			}
			for (Species sp : nextGenSpecies) {
				if (!cappedSpecies.contains(sp)) {
					int nextGenPop = (int) (sp.getSpeciesFitness()
							* popSizeLeft / sumFitness);
					sp.setNextGenPopulation(nextGenPop);
				}
			}
			System.out.println("Done speciation");

			postSpeciation(nextGenSpecies);

			// modify the speciationThreshold
			if (Constants.autoSpeciationThreshold) {
				int nSpecies = nextGenSpecies.size();
				if (nSpecies < Constants.targetNSpecies) {
					Constants.speciationThreshold -= Constants.speciationThresholdMod;
				} else if (nSpecies > Constants.targetNSpecies) {
					Constants.speciationThreshold += Constants.speciationThresholdMod;
				}
				Constants.speciationThreshold = Math.max(
						Constants.speciationThreshold,
						Constants.speciationThresholdMin);
			}

			// calculate fitness including sharing
			for (int i = 0; i < nextGen.length; i++) {
				for (Species sp : nextGenSpecies) {
					if (nextGen[i].spicies == sp.representative) {
						fitness[i] = nextGen[i].getFitness()
								/ sp.individuals.size();
					}
				}

			}

			// display metrics
			Individual best1 = null;
			Individual best2 = null;
			Individual best3 = null;
			double avgFitness = 0;
			double avgTemplates = 0;
			double avgSD = 0;
			for (int i = 0; i < nextGen.length; i++) {
				if (best1 == null
						|| best1.getFitness() < nextGen[i].getFitness()) {
					best1 = nextGen[i];
				}
				avgFitness += nextGen[i].getFitness();
				avgTemplates += nextGen[i].getNumberOfTemplates();
				avgSD += nextGen[i].getStandardDeviationOfLogK();
			}
			avgFitness /= nextGen.length;
			avgTemplates /= nextGen.length;
			avgSD /= nextGen.length;
			for (int i = 0; i < nextGen.length; i++) {
				if (best2 == null
						|| best2.getFitness() < nextGen[i].getFitness()
						&& nextGen[i] != best1) {
					best2 = nextGen[i];
				}
			}
			for (int i = 0; i < nextGen.length; i++) {
				if (best3 == null
						|| best3.getFitness() < nextGen[i].getFitness()
						&& nextGen[i] != best1 && nextGen[i] != best2) {
					best3 = nextGen[i];
				}
			}

			speciesData[0][generation] = speciesVisualData.get(generation)
					.size();
			speciesData[1][generation] = Constants.speciationThreshold * 10;

			
			int nInspectSpecies = 5;
			double[][] newFitnessData = new double[nInspectSpecies * 2][speciesVisualData
					.size()];
			for (int i = 0; i < speciesVisualData.size(); i++) {
				ArrayList<Species> thisGeneSpecies = speciesVisualData.get(i);
				ArrayList<Species> bestSpeciesList = new ArrayList<Species>();
				for (int j = 0; j < nInspectSpecies; j++) {
					Species bestSpecies = null;
					for (Species sp : thisGeneSpecies) {
						if (!bestSpeciesList.contains(sp)) {
							if (bestSpecies == null
									|| bestSpecies.getBestIndividual()
											.getFitness() < sp
											.getBestIndividual().getFitness()) {
								bestSpecies = sp;
							}
						}
					}
					if (bestSpecies == null) {
						newFitnessData[j * 2][i] = 0;
						newFitnessData[j * 2 + 1][i] = 0;
					} else {
						newFitnessData[j * 2][i] = bestSpecies
								.getBestIndividual().getFitness();
						newFitnessData[j * 2 + 1][i] = bestSpecies
								.getTotalFitness()
								/ bestSpecies.individuals.size();
						bestSpeciesList.add(bestSpecies);
					}
				}
			}

			String[] names = new String[nInspectSpecies * 2];
			for (int i = 0; i < nInspectSpecies; i++) {
				names[i * 2] = "Best " + (i + 1);
				names[i * 2 + 1] = "Avg " + (i + 1);
			}


			

				
			
			logger.saveToFile();

		}

		logger.logToMemory("Innovations:");
		for (String key : innovations.keySet()) {
			logger.logToMemory(key + ":" + innovations.get(key));
		}
		logger.logToMemory("Node names used:");
		for (String key : nodeNames.keySet()) {
			logger.logToMemory(key + ":" + nodeNames.get(key));
		}
	}

	protected void postSpeciation(ArrayList<Species> nextGenSpecies) {
		// TODO Auto-generated method stub

	}

	protected void postEvaluation(Individual[] nextGen) {

	}

	/**
	 * Should modify futures, nextGen and logger by side effect. In particular,
	 * it should give their fitness to nextGen elements
	 * 
	 * @param futures
	 * @param nextGen
	 * @param logger
	 */
	protected void launchEvaluation(Individual[] nextGen, LoggerNEAT logger) {
		OligoSystemGeneral[] oligoSystems = new OligoSystemGeneral[nextGen.length];
		for (int i = 0; i < nextGen.length; i++) {
			oligoSystems[i] = nextGen[i].getOligoModel();
		}
		FitnessResult[] results = evaluationService
				.evaluateFitness(oligoSystems);
		for (int i = 0; i < results.length; i++) {
			nextGen[i].fitnessResult = results[i];
		}
	}

	public double compDistance(Individual indiv1, Individual indiv2) {
		CompatibilityDistance distance = CompatibilityDistance(indiv1, indiv2);
		return distance.distance();
	}

	public CompatibilityDistance CompatibilityDistance(Individual indiv1,
			Individual indiv2) {
		int nExcess = 0;
		int nDisjoint = 0;
		double avgWeightDifference = 0;
		int nMatches = 0;
		int N = Math.max(indiv1.getNEnabledConnections(),
				indiv2.getNEnabledConnections());
		for (int i = innovations.size(); i >= 1; i--) {
			Connection conn1 = indiv1.getConnection(i);
			Connection conn2 = indiv2.getConnection(i);
			if ((conn1 == null || !conn1.enabled)
					&& (conn2 == null || !conn2.enabled)) {
				continue;
			}
			if ((conn1 == null || !conn1.enabled)
					|| (conn2 == null || !conn2.enabled)) {
				if (nMatches == 0) {
					nExcess++;
				} else {
					nDisjoint++;
				}
			} else {
				nMatches++;
				avgWeightDifference += Math.abs(conn1.parameter
						/ conn1.from.parameter - conn2.parameter
						/ conn2.from.parameter);
			}
		}
		if (nMatches > 0) {
			avgWeightDifference = (double) avgWeightDifference / nMatches;
		}
		return new CompatibilityDistance(nExcess, nDisjoint,
				avgWeightDifference, N);
	}

	public Individual crossOver1Point(Individual indiv1, Individual indiv2)
	throws CloneNotSupportedException {
Individual tmp = getNewIndividual(indiv1.innovations, indiv1.nodeNames,
		-2, 0);
int genomeLength = innovations.size();
for (int i = innovations.size(); i >= 1; i--) {
	Connection conn1 = indiv1.getConnection(i);
	Connection conn2 = indiv2.getConnection(i);
	if (conn1 == null && conn2 == null) {
		genomeLength--;
	} else {
		break;
	}
}
if (genomeLength > 0) {
	int start = 1 + rand.nextInt(genomeLength);
	int end = genomeLength;
	for (int i = 1; i < start; i++) {
		Connection conn = indiv1.getConnection(i);
		if (conn != null) {
			tmp.addConnection(conn.from, conn.to, conn.enabled,
					conn.parameter);
		}
	}
	for (int i = start; i < end; i++) {
		Connection conn = indiv2.getConnection(i);
		if (conn != null) {
			tmp.addConnection(conn.from, conn.to, conn.enabled,
					conn.parameter);
		}
	}
	for (int i = end; i <= genomeLength; i++) {
		Connection conn = indiv1.getConnection(i);
		if (conn != null) {
			tmp.addConnection(conn.from, conn.to, conn.enabled,
					conn.parameter);
		}
	}
} else {
	tmp = indiv1;
}
Individual child = getNewIndividual(this.innovations, this.nodeNames,
		-2, 0);
for (Connection connection : tmp.connectionGenes) {
	if (child.getNode(connection.from.name) == null) {
		child.nodeGenes.add(connection.from.clone());
	}
	if (child.getNode(connection.to.name) == null) {
		child.nodeGenes.add(connection.to.clone());
	}
	child.addConnection(child.getNode(connection.from.name),
			child.getNode(connection.to.name), connection.enabled,
			connection.parameter);
}

return child;
}

public Individual crossOver2Points(Individual indiv1, Individual indiv2)
	throws CloneNotSupportedException {
Individual tmp = getNewIndividual(indiv1.innovations, indiv1.nodeNames,
		-2, 0);
int genomeLength = innovations.size();
for (int i = innovations.size(); i >= 1; i--) {
	Connection conn1 = indiv1.getConnection(i);
	Connection conn2 = indiv2.getConnection(i);
	if (conn1 == null && conn2 == null) {
		genomeLength--;
	} else {
		break;
	}
}
if (genomeLength > 0) {
	int start = 1 + rand.nextInt(genomeLength);
	int end = 1 + rand.nextInt(genomeLength);
	if (start > end) {
		int temp = start;
		start = end;
		end = temp;
	}
	for (int i = 1; i < start; i++) {
		Connection conn = indiv1.getConnection(i);
		if (conn != null) {
			tmp.addConnection(conn.from, conn.to, conn.enabled,
					conn.parameter);
		}
	}
	for (int i = start; i < end; i++) {
		Connection conn = indiv2.getConnection(i);
		if (conn != null) {
			tmp.addConnection(conn.from, conn.to, conn.enabled,
					conn.parameter);
		}
	}
	for (int i = end; i <= genomeLength; i++) {
		Connection conn = indiv1.getConnection(i);
		if (conn != null) {
			tmp.addConnection(conn.from, conn.to, conn.enabled,
					conn.parameter);
		}
	}
} else {
	tmp = indiv1;
}
Individual child = getNewIndividual(this.innovations, this.nodeNames,
		-2, 0);
for (Connection connection : tmp.connectionGenes) {
	if (child.getNode(connection.from.name) == null) {
		child.nodeGenes.add(connection.from.clone());
	}
	if (child.getNode(connection.to.name) == null) {
		child.nodeGenes.add(connection.to.clone());
	}
	child.addConnection(child.getNode(connection.from.name),
			child.getNode(connection.to.name), connection.enabled,
			connection.parameter);
}

return child;
}
	
	public Individual crossOver(Individual indiv1, Individual indiv2)
			throws CloneNotSupportedException {
		Individual tmp = getNewIndividual(indiv1.innovations, indiv1.nodeNames,
				-2, 0);
		for (int i = 1; i <= innovations.size(); i++) {
			Connection conn1 = indiv1.getConnection(i);
			Connection conn2 = indiv2.getConnection(i);
			if (conn1 != null && conn2 != null) {
				boolean enabled = true;
				if (!(conn1.enabled && conn2.enabled)
						&& rand.nextDouble() < Constants.probGeneDisabled) {
					enabled = false;
				}
				tmp.addConnection(conn1.from, conn1.to, enabled,
						rand.nextBoolean() ? conn1.parameter : conn2.parameter);
			} else if (conn1 != null
					&& indiv1.getFitness() >= indiv2.getFitness()) {
				tmp.addConnection(conn1.from, conn1.to, conn1.enabled,
						conn1.parameter);
			} else if (conn2 != null
					&& indiv2.getFitness() >= indiv1.getFitness()) {
				tmp.addConnection(conn2.from, conn2.to, conn2.enabled,
						conn2.parameter);
			}
		}
		Individual child = getNewIndividual(this.innovations, this.nodeNames,
				-2, 0);
		for (Connection connection : tmp.connectionGenes) {
			if (child.getNode(connection.from.name) == null) {
				child.nodeGenes.add(connection.from.clone());
			}
			if (child.getNode(connection.to.name) == null) {
				child.nodeGenes.add(connection.to.clone());
			}
			child.addConnection(child.getNode(connection.from.name),
					child.getNode(connection.to.name), connection.enabled,
					connection.parameter);
		}
		return child;
	}

	private Individual[] selectCrossoverParents(ArrayList<Individual> curGen) {
		double maxFitness = -Double.MAX_VALUE;
		Individual parent1 = null;
		Individual parent2 = null;
		System.out.println(curGen.size());
		if (curGen.size() == 1) {
			return new Individual[] { curGen.get(0), curGen.get(0) };
		}

		for (int k = 0; k < Constants.tournamentSize; k++) {
			int winnerIndiv = this.rand.nextInt(curGen.size());
			Individual i = curGen.get(winnerIndiv);
			if (i.getFitness() > maxFitness) {
				parent1 = i;
				maxFitness = i.getFitness();
			}
		}
		maxFitness = -Double.MAX_VALUE;

		for (int k = 0; k < Constants.tournamentSize; k++) {
			Individual i = null;
			do {
				int winnerIndiv = this.rand.nextInt(curGen.size());
				i = curGen.get(winnerIndiv);
			} while (i == parent1);

			if (i.getFitness() > maxFitness) {
				parent2 = i;
				maxFitness = i.getFitness();
			}
		}

		return new Individual[] { parent1, parent2 };
	}

	private int[] selectCrossoverParents(double[] fitness) {
		int xoverIndex1 = -1, xoverIndex2 = -1;
		int winnerIndiv;
		int selectedIndividuals[] = new int[2];
		double sumFitness;
		double range[] = new double[Constants.popSize];
		double randomFitness;
		double maxFitness;
		do {
			if (GAConstants.gSelectionMethod == 1) { // Roulette selection
				sumFitness = 0;
				range[0] = 0;
				for (int i = 0; i < Constants.popSize; ++i) {
					sumFitness += fitness[i];
					range[i] = sumFitness;
				}

				randomFitness = sumFitness * this.rand.nextDouble();
				for (int i = 0; i < Constants.popSize; ++i) {
					if (range[i] > randomFitness) {
						xoverIndex1 = i;
						break;
					}
				}

				randomFitness = sumFitness * this.rand.nextDouble();
				for (int i = 0; i < Constants.popSize; ++i) {
					if (range[i] > randomFitness) {
						xoverIndex2 = i;
						break;
					}
				}
			} else {// if (gSelectionMethod==2){ // Tournament Selection
				maxFitness = -Double.MAX_VALUE;

				for (int k = 0; k < GAConstants.gTournamentSize; ++k) {
					winnerIndiv = this.rand.nextInt(Constants.popSize);
					if (fitness[winnerIndiv] > maxFitness) {
						xoverIndex1 = winnerIndiv;
						maxFitness = fitness[winnerIndiv];
					}
				}

				maxFitness = -Double.MAX_VALUE;

				for (int k = 0; k < GAConstants.gTournamentSize; ++k) {
					winnerIndiv = this.rand.nextInt(Constants.popSize);
					if (fitness[winnerIndiv] > maxFitness) {
						xoverIndex2 = winnerIndiv;
						maxFitness = fitness[winnerIndiv];
					}
				}
			}
		} while (xoverIndex1 == xoverIndex2);
		selectedIndividuals[0] = xoverIndex1;
		selectedIndividuals[1] = xoverIndex2;
		return (selectedIndividuals);
	}

	protected Individual clone(Individual indiv)
			throws CloneNotSupportedException {
		Individual clone = getNewIndividual(indiv.innovations, indiv.nodeNames,
				indiv.generationIndex, indiv.individualIndex);
		for (Node node : indiv.nodeGenes) {
			clone.nodeGenes.add(node.clone());
		}
		for (Connection connection : indiv.connectionGenes) {
			clone.addConnection(clone.getNode(connection.from.name),
					clone.getNode(connection.to.name), connection.enabled,
					connection.parameter);
		}
		clone.exo = indiv.exo;
		clone.pol = indiv.pol;
		clone.nick = indiv.nick;
		clone.config = indiv.config;
		clone.parent1 = indiv.parent1;
		clone.parent2 = indiv.parent2;
		clone.mutationInfo = indiv.mutationInfo;
		return clone;
	}

}